#include <bits/stdc++.h>

#define N 10005

using namespace std;

struct edge{
    int to;
    int val;
};

vector <edge> G[N];
int dis[N];
int n, m, s;

void addedge(int fr, int to, int dis){
    G[fr].push_back((edge){to, dis});
}

//两个选一个调用
void dijkstra(int scr){
    bool find[N] = {false}; //是否最短
    dis[scr] = 0; //到自己距离为0
    //find[scr] = true;

    int from[N];
    for(int x = 1; x <= n; x++){
        int u = -1;
        for(int i = 1; i <= n; i++){
            if(!find[i] && (u == -1 || dis[u] > dis[i])){
                u = i;
            }
        }
        if(u == -1) break;
        find[u] = true;
        for(edge v: G[u]){
            if(dis[v.to] > dis[u] + v.val){
                dis[v.to] = dis[u] + v.val;
            }
        }
    }
}

struct node{
    int dis;
    int id;
    //重载<运算符
    bool operator<(const node& other)const{
        return dis > other.dis;
    }
};

void dijkstra_heap(int scr){
    priority_queue<node> pq;
    bool find[N] = {false};
    dis[scr] = 0;
    pq.push((node){0, scr}); //dis, id

    while(!pq.empty()){
        node u = pq.top();  pq.pop();
        if(u.dis > dis[u.id])   continue;
        for(edge& e : G[u.id]){
            if (dis[e.to] > dis[u.id] + e.val) {
                dis[e.to] = dis[u.id] + e.val;
                pq.push((node){dis[e.to], e.to});
            }
        }
    }
}

int main(){
    cin >> n >> m >> s;
    fill(dis, dis+n+1, 0x7FFFFFFF);
    int u, v, val;
    for(int i = 1; i <= m; i++){
        scanf("%d %d %d", &u, &v, &val);
        addedge(u, v, val);
    }
    dijkstra_heap(s);
    for(int i = 1; i <= n; i++){
        cout << dis[i] << " ";
    }
    return 0;
}